package leecode;

import org.apache.kafka.common.protocol.types.Field;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 *
 *
 * @author qingyan 2021-07-02
 */
public class Question22 {

    public static void main(String[] args) {
        Question22 q22 = new Question22();
        List<String> strings = q22.generateParenthesis(10);
        System.out.println(Arrays.toString(strings.toArray()));
    }

    public List<String> generateParenthesis(int n) {
        return dg(n);
    }


    /*方案一、递归 */
    /**
     * 递归
     * i: 当前遍历到位置
     * n: 字符总长度
     * score: 当前得分，令 '(' 为 1， ')' 为 -1
     * max: 最大得分值
     * path: 当前的拼接结果
     * ans: 最终结果集
     */
    List<String> dg(int n) {
        List<String> ans = new ArrayList<>();
        dfs(n, 0, 0, "", ans);
        return ans;
    }

    void dfs(int n, int left, int right, String path, List<String> ans) {
        if (path.length() == 2 * n){
            ans.add(path);
        }
        if (left < n) {
            dfs( n, left + 1, right, path + "(", ans);
        }
        if (right < left) {
            dfs( n, left, right + 1, path + ")", ans);
        }
    }


    /*
        方案二、动态规划
        当我们要给出n个括号对组成的结果集 f(n)时，在这个结果中，所有字符串的第一个元素必然是 "("
        那么必然有另一个与之匹配的右括号 ")"
        那么还有 n-1 个括号对需要安放
        这 n-1 个括号对中，可以有 j 个括号对位于上述这对括号的内部，那么剩余的 n-1-j 个括号对都在上述括号对右侧
        j的取值范围应该是 [0, n-1]
        所以在计算f(n)时， 我们是需要知道 f(0), f(1), ... f(n-1)的结果的，因此需要用map保存dp过程中的每一个结果

        dp[i]="("+dp[m]+")"+dp[k]
        其中m+k=i-1
    */
    List<String> dp(int n) {
        List<String>[] dp = new List[n + 1];
        List<String> dp0 = new ArrayList<>();
        dp0.add("");
        dp[0] = dp0;
        for (int i = 1; i <= n; i++) {
            List<String> cur = new ArrayList<>();
            for (int m = 0; m < i; m++) {
                int k = i - 1 - m;
                List<String> str1 = dp[m];
                List<String> str2 = dp[k];
                for (String s1 : str1) {
                    for (String s2 : str2) {
                        cur.add("(" + s1 + ")" + s2);
                    }
                }
            }
            dp[i] = cur;
        }
        return dp[n];
    }

}
